/* 二叉链表法 */

template <typename Comparable>
class BinarySearchTree
{

public:
    // 三个构造函数重载
    BinarySearchTree();
    BinarySearchTree( const BinarySearchTree & rhs) : root{nullptr} { root = clone(rhs.root); }
    BinarySearchTree( BinarySearchTree && rhs);
    /*直接用清空函数来析构*/
    ~BinarySearchTree() { makeEmpty(); };
    

    /* 传引用调用：
     * 公有部分中声明单参或无参方法，在函数体中加入root参数（进行包装）
     * 再调用私有部分的双参数方法
     * （因为外部无法访问根，所以用这个方法实现全树查找）
     */
    const Comparable & findMin() const;     // 找最小值
    const Comparable & findMax() const;     // 找最大值
    int height() { return height(root); }   // 返回深度
    bool contains(const Comparable & x) const { return contains(x,root); }  // 检测是否包含值为x的节点
    bool isEmpty() const { isEmpty(root); };    // 判空
    // 打印（一般用的都是标准输出流，不排除其它情况）
    void printTree( ostream & out = cout ) const
    {
        if ( isEmpty() )
            out << "树是空的" << std::endl;
        else
            printTree(root,out);
    } 

    void makeEmpty() { makeEmpty(root); }    // 删除树
    void insert (const Comparable & x) { insert(x,root); }   // 插入节点（左值）
    void insert ( Comparable && x ) { insert (x,root); }     // 插入节点（右值）
    void remove ( const Comparable & x ) { remove(x,root); } // 删除值为x的节点

    BinarySearchTree & operator= (const BinarySearchTree & rhs);    // 树的相互赋值（左值）
    BinarySearchTree & operator= ( BinarySearchTree && rhs );       // 树的相互赋值（右值）

private:
    // 节点的结构声明
    struct BinaryNode
    {
        Comparable element; //内容
        //左右子节点
        BinaryNode * left;
        BinaryNode * right;
        //赋值构造函数
        BinaryNode (const Comparable & theElement, BinaryNode * lt, BinaryNode * rt) : element {theElement}, left{lt}, right{rt} {}
    };

    // 根节点
    BinaryNode *root;
    
    /*插入节点（左值）*/
    void insert (const Comparable & x, BinaryNode *& t)
    {
        /* 找到位置，进行插入
         * （因为原本所有树叶节点均有左右空指针，所以不需要重新设置指针）
         * 若出现重复值，则保留在节点记录中，而不是真正创建一个节点
        */
        if (t == nullptr)
            t = new BinaryNode{ x, nullptr,nullptr };
        /*递归遍历*/
        else if (x < t->element)
            insert (x,t->left);
        else if (t->element < x)
            insert (x,t->right);
        else
            ;//什么也不做
    }
    /*插入节点（右值）*/
    void insert( Comparable && x, BinaryNode *& t)
    {
        if (t == nullptr)
            t = new BinaryNode{ std::move(x), nullptr,nullptr };
        else if (x < t->element)
            insert ( std::move(x) , t->left);
        else if (t->element < x)
            insert ( std::move(x) , t->right);
        else
            ;//什么也不做
    }
    /*移除节点*/
    void remove( const Comparable & x, BinaryNode *& t )
    {
        /* 找不到节点，则什么也不做
         *（判空操作应当是独立的if，因为空对象无法比较值）
         */
        if(t == nullptr)
            return;
        /*递归查找等于x的节点*/
        if(x < t->element)
            remove(x,t->left);
        else if(t->element < x)
            remove(x,t->right);
        /* 若其不为树叶，则取最小右树叶
         * 然后递归调用，删除最小右树叶
         * 其它节点不变，最终还是二叉树
        */
        else if(t->left != nullptr && t->right != nullptr)
        {
            t->element = findMin (t->right) -> element;
            remove(t->element, t->right);
        }
        /* 若其为树叶，则直接进行指针操作 + 析构节点
         * 若其只有一个子节点，则直接将其替换为t，然后删除t
        */
        else
        {
            BinaryNode * oldNode = t;       //中间存储量
            t = (t->left != nullptr) ? t->left : t->right;
            delete oldNode;
        }
    }

    /*查找节点的两种方法*/
    BinaryNode * findMin(BinaryNode *t) const
    {
        /*递归遍历，查找最左侧的后代树叶节点*/
        if (t == nullptr)
            return nullptr;
        if (t ->left == nullptr)
            return t;
        return findMin( t->left);
    }
    BinaryNode * findMax(BinaryNode *t) const
    {
        /*循环遍历，查找最右侧的后代树叶节点*/
        if( t!= nullptr )
            while(t->right != nullptr)
                t = t->right;
        return t;
    }

    /*计算高度（后序遍历）*/
    int height (BinaryNode *t)
    {
        if (t==nullptr)
            return -1;
        else
            return 1+max(height(t->left), height(t->right) );
    }

    /*测试是否包含节点*/
    bool contains( const Comparable & x, BinaryNode *t ) const
    {
        if (t == nullptr)
            return false;
        /*递归遍历，查找传入节点t*/
        else if (x < t->element)
            return contains(x,t->left);
        else if (t->element < x)
            return contains(x,t->right);
        /*当前节点就是查找节点t*/
        else
            return true;
    }

    /*判空树（看起来没必要，不过要遵守代码规范，万一以后要扩展功能呢？）*/
    bool isEmpty (BinaryNode *& t)
    {
        return (t != nullptr) ;
    }

    /*清空树*/
    void makeEmpty(BinaryNode *& t)
    {   
        /*递归清除所有子节点（调用次数 == 节点数量）*/
        if (t != nullptr)
        {
            makeEmpty (t->left );
            makeEmpty (t->right);
            delete t;
        }
        /*最后清除当前节点（顺序很重要）*/
        t = nullptr;
    }
    
    /*打印树（利用前序遍历）（我自己写的，注意可能有错误）*/
    void printTree(BinaryNode *t, ostream & out) const
    {
        if (t == nullptr)
            return ;
        else
            out << "\t" << t->element << std::endl ; //错误，不能保持缩进。也许应该用一个静态类成员？毕竟theSize方法他也没写
            printTree(t->left, out);
            printTree(t->right, out);
    }

    /*复制树*/
    BinaryNode * clone(BinaryNode * t) const
    {
        if(t == nullptr)
            return nullptr;
        else 
            return new BinaryNode { t->element, clone(t->left), clone(t->right) };
    }
};

